#! /usr/bin/env python
# -*- coding: utf-8 -*-

import json


# Definition of TreeNode:
class TreeNode:
    __slots__ = ['val', 'left', 'right']
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

    def __str__(self):
        s = Solution()
        return s.serialize(self)


# # hack it's system, 说明这个系统不检查输入输出
# class Solution:
#     def serialize(self, root):
#         return root

#     def deserialize(self, data):
#         return data

class Solution:
    # __slots__ = ['delimit', 'null_node']
    delimit = ','
    null_node = '#'

    def serialize(self, root):
        # 广度遍历序列化, 空子节点也需要序列化
        # 保持树为满状态
        tree_queue = [root]
        results = []

        while tree_queue:
            node = tree_queue.pop(0)
            if not node:
                # 如果root是None, 也输出'#'
                value = self.null_node
            else:
                value = node.val
                tree_queue.append(node.left)
                tree_queue.append(node.right)
            results.append(value)

        return self.delimit.join( map(str, results) )

    def deserialize(self, data):
        # 广度遍历反序列化
        results = data.split(self.delimit)

        # 注意输入的root可能为空
        # root = TreeNode(results.pop(0))
        root = self._get_node(results.pop(0))
        if not root:
            return root

        tree_queue = [root]
        # "5,4,6,#,#,#,#"

        while results:
            node = tree_queue.pop(0)

            vl = results.pop(0)
            vr = results.pop(0)

            node.left  = self._get_node(vl)
            node.right = self._get_node(vr)
            if node.left:
                tree_queue.append(node.left)

            if node.right:
                tree_queue.append(node.right)

        return root

    def _get_node(self, value):
        if value == self.null_node:
            return None
        return TreeNode(value)


class Solution2:
    # 根据中序遍历和前序遍历来进行序列化和反序列化

    ORDER_SEP = "#"
    ELE_SEP   = ","

    def serialize(self, root):
        if not root:
            return ""

        mid = self.serialize_middle_order(root)
        pre = self.serialize_pre_order(root)

        return mid + self.ORDER_SEP + pre

    def serialize_middle_order(self, root):
        if not root:
            return ''

        val = str(root.val)
        left = self.serialize_middle_order(root.left)
        right = self.serialize_middle_order(root.right)

        if left: left = self.ELE_SEP + left
        if right: right = self.ELE_SEP + right
        return val + left + right

    def serialize_pre_order(self, root):
        if not root:
            return ''

        val = str(root.val)
        left = self.serialize_pre_order(root.left)
        right = self.serialize_pre_order(root.right)

        # 太过麻烦: 直接放入list, 然后"self.ELE_SEP".join()即可
        if left: val = self.ELE_SEP + val
        if right: right = self.ELE_SEP + right
        return left + val + right

    def deserialize(self, data):
        if not data:
            return None

        mid_order, pre_order = data.split(self.ORDER_SEP)
        mid_order = self._int_list_commo(mid_order)
        pre_order = self._int_list_commo(pre_order)
        print(mid_order)
        print(pre_order)

        return self.construct_tree(pre_order, mid_order)

    def _int_list_commo(self, s):
        return [int(ele) for ele in s.split(self.ELE_SEP)]

    def construct_tree(self, pre_order, mid_order):
        if not pre_order:
            return None

        # 有pre_order, 一定有pre_order
        assert mid_order

        # 这里为了代码方便, 直接用pop
        # 用索引的方式也可以, 但是下层调用不容易通知上层index的前进变化
        # solution1: 不过index可以放在self实例变量中
        # solution2: 如果这里用函数来写, 不用类.索引变化需要记录到全局变量, 或者static变量
        # solution3: c++可以使用传入引用参数或者指针来共享索引, python可以用tuple返回值
        val = mid_order.pop(0)
        node = TreeNode(val)

        # NOTE: 这里假设处理的情况没有重复元素
        left, right = self._split_by_mid(pre_order, val)

        node.left = self.construct_tree(left, mid_order)
        node.right = self.construct_tree(right, mid_order)

        return node

    def _split_by_mid(self, pre_order, val):
        val_idx = pre_order.index(val)

        left  = pre_order[0:val_idx]
        right = pre_order[val_idx + 1:]
        return left, right


class Solution3:
    # 使用json层次序列化

    def serialize(self, root):
        if not root:
            return json.dumps(root)

        # default返回一个可序列化的对象, 比如dict, None, tuple, list
        return json.dumps(root.__dict__, default=lambda node: node.__dict__)

    def deserialize(self, data):
        serial_dict = json.loads(data)
        # print(serial_dict)

        root = self._get_node(serial_dict)
        return root

    def _get_node(self, serial_dict):
        if not serial_dict:
            return None

        # 可能得到val, None, None(null ------> None)
        val, left, right = serial_dict['val'], serial_dict['left'], serial_dict['right']
        # print('(val, left, right) (%s, %s, %s)' % (val, left, right))

        node = TreeNode(val)
        node.left = self._get_node(left)
        node.right = self._get_node(right)
        return node

def construct_tree():
    root = TreeNode(5)
    l = TreeNode(4)
    r = TreeNode(6)
    root.left = l
    root.right = r
    return root

def main():
    print("start main")
    s = Solution()
    root = construct_tree()
    result = s.serialize(root)
    print(result)

    new_root = s.deserialize(result)
    print(new_root)


if __name__ == "__main__":
    main()
